#include <math.h>

#include "base/Simulator.h"
#include "base/simconstants.h"
#include "base/simtypes.h"
#include "mem/CacheHash.h"

NEW_DELETE_OPERATORS_CPP(CacheHash,100);


unsigned int CacheHash::hash (VA addr) const {
    return ADDR_UINT32(((addr >> index_shift) & index_mask) % hashsize);
}

// this func should not be used, we just use it as a place holder...
static unsigned int dummy (VA addr) {
    ASSERT(false);
    return addr;
}

CacheHash::CacheHash (Entity* _owner,
                      Logger* _log,
                      int     _size,
                      uint    _block_size,
                      uint    _assoc,
                      uint    _vcsize) :
    HashTable<VA, CacheEntry*>((_assoc > 0) ? _size/_assoc/_block_size : 1,
                               dummy),
    owner(_owner),
    log(_log),
    size(_size),
    assoc(_assoc),
    block_size(_block_size),
    vc_size(_vcsize),
    victimCache()
{
    if (assoc == 0) {
        // fully associative means assoc = size/block_size = # entries
        assoc = size / block_size;
    }

    this->hashsize = size/assoc/block_size;
    
    assocCounts = (int*)CALLOC(hashsize, sizeof(uint));

    for (uint i = 0; i < hashsize; i++) {
        assocCounts[i] = 0;
    }

    index_shift = (uint)log2(block_size);
    index_mask = (size / block_size - 1) >> (uint)log2(assoc);

    // disable warning on excessive load factor, which is bounded by
    // the constant size of the associativity
    threshold = (uint)-1;
}


CacheHash::~CacheHash () {
    FREE(assocCounts);
}

List<CacheEntry*>* CacheHash::retrieve (VA addr) const {
    List<CacheEntry*>* result = NEW List<CacheEntry*>;
    for (HashTableNode<VA,CacheEntry*>* walk = getTable()[hash(addr)];
         walk != NULL; walk = walk->next)
    {
        if (walk->key == addr) {
            result->add(walk->data);
        }
    }
    result->sort(CacheEntryAgeLessThan());
    return result;
}

bool CacheHash::contains (VA addr) const {
    for (HashTableNode<VA,CacheEntry*>* walk = getTable()[hash(addr)];
         walk != NULL; walk = walk->next)
    {
        if (walk->key == addr) {
            return true;
        }
    }
    return false;
}

List<CacheEntry*>* CacheHash::retrieveSet (VA addr) const {
    List<CacheEntry*>* result = NEW List<CacheEntry*>;
    for (HashTableNode<VA,CacheEntry*>* walk = getTable()[hash(addr)];
         walk != NULL; walk = walk->next)
    {
        result->add(walk->data);
    }
    result->sort(CacheEntryAgeLessThan());
    return result;
}

struct CHAvailable CacheHash::spaceAvailable (VA const addr) const {
    ASSERT((uint)(assocCounts[hash(addr)]) <= assoc);
    struct CHAvailable result;
    result.associativity = assoc - assocCounts[hash(addr)];

    ASSERT(victimCache.size() <= vc_size);
    result.victimCache = vc_size - victimCache.size();

#ifdef XXX_ANM
    log->i("%lli:%s %llx space: (%i %i)\n",
           global_sim->getSimclock(),
           owner->getName(),
           addr,
           assocCounts[hash(addr)],
           victimCache.size());
#endif
    return result;
}


void CacheHash::insert (VA addr, CacheEntry* data) {
    data->checkSanity();
    
    int place = hash(addr);

    // Notes:
    //   o we check for negative assocCounts here just to make sure that doesnt
    //     occur
    //   o if you get this assert, that means you had an associative overflow
    //
    if (((uint)assocCounts[place] >= assoc || assocCounts[place] < 0) &&
        (uint)victimCache.size() >= vc_size)
    {
        log->e("%lli:%s No space in CacheHash (%llx): %i:%i %i:%i\n",
                                   global_sim->getSimclock(),
                                   owner->getName(),
                                   addr,
                                   assocCounts[place],
                                   assoc,
                                   victimCache.size(),
                                   vc_size);
    }

    // do we need to swap it into the victim cache?
    if ((uint)assocCounts[place] >= assoc) {
        // find a "victim" to move from the cache to the victim cache...

        CacheEntry* victim = NULL;
        HashTableNode<VA, CacheEntry*>* walk = table[place];

        while (walk) {
            if (walk->data->isInVictimCache() == false) {
                if (!victim || walk->data->getAge() < victim->getAge()) {
                    victim = walk->data;
                }
            }
            walk = walk->next;
        }

        victim->setInVictimCache(true);
        victimCache.add(victim);

#ifdef XXX_ANM
        log->i("%lli:%s added (%0x) %llx: %i:%i %i:%i\n",
               global_sim->getSimclock(),
               owner->getName(),
               (uint)victim,
               victim->getAddress(),
               assocCounts[place],
               assoc,
               victimCache.size(),
               vc_size);
#endif
    } else {
        assocCounts[place]++;
    }
#ifdef XXX_ANM
        log->i("%lli:%s inserted (%0x) %llx\n",
               global_sim->getSimclock(),
               owner->getName(),
               (uint)data,
               addr);
#endif

    data->setInVictimCache(false);
    data->location = this;
    HashTable<VA, CacheEntry*>::insert(addr, data);
}

// visitSet
//
// visit each set in the cache, providing a list of the cacheentries in that
// set.
//
// they are sorted by addr then by nesting level. remove some from the list
// and they will be removed from the set
//
void CacheHash::visitSet (void (*visitor)(List<CacheEntry*>*, void*),
                          void* data)
{
    List<CacheEntry*>* list = NEW List<CacheEntry*>;

    for (uint place = 0; place < htsize; place++) {
        HashTableNode<VA, CacheEntry*>* walk = table[place];

        list->clear();

        while (walk) {
            list->add(walk->data);
            log->d("visitSet: adding %08llx %s\n",
                   walk->data->getAddress(),
                   walk->data->flags->str());
            walk = walk->next;
        }

        int origSize = list->size();

        // sort list by addr then by nestinglevel
        //
        list->sort(CacheEntryFlagsLessThan());

        visitor(list, data);

        // see if they deleted anything out of the list...
        //
        log->d("visitSet: %i / %i entries\n",
               list->size(),
               origSize);

        walk = table[place];
        HashTableNode<VA, CacheEntry*>* prev = NULL;
        while (walk) {
            List<CacheEntry*>::iterator i = list->begin();
            for (; i != list->end(); i++) {
                ASSERT(walk->data->location == this);
                if ((uint*)*i == (uint*)walk->data) { // ptr equivalence
                    break;
                }
            }
            if (i == list->end()) {
                log->d("visitSet: removing %08llx\n", walk->data->getAddress());
                CacheEntry* old = walk->data;
                remove(walk->data->getAddress(), &walk, &prev); 
                delete old;
            } else {
                log->d("visitSet: leaving %08llx %s\n",
                       walk->data->getAddress(),
                       walk->data->flags->str());
                prev = walk;
                walk = walk->next;
            }
        }
    }

    delete list;
}

void CacheHash::remove (CacheEntry* ce) {
    // unlink it from the list...
    bool done = false;
    VA addr = ce->getAddress();

    HashTableNode<VA,CacheEntry*>* walk = getTable()[hash(addr)];
    HashTableNode<VA,CacheEntry*>* prev = NULL;
    while (walk) {
        if (walk->key == addr && ((uint)walk->data) == ((uint)ce)) {
            ASSERT(!done);
            done = true;
            remove(addr, &walk, &prev);

            ASSERT(ce->location == NULL);
        }
        if (walk) {
             prev = walk;
             walk = walk->next;
        }
    }
    ASSERT(done);
}

void CacheHash::implicitRemoval (VA addr, CacheEntry* entry) {
    ASSERT(entry); // when are you calling this w/o an entry?

    if (entry->isInVictimCache()) {
        uint size = victimCache.size();
        victimCache.remove(entry); // this should use pointer ==
        entry->setInVictimCache(false);
        ASSERT(size == victimCache.size() + 1);
    } else {
        assocCounts[hash(addr)]--;
    }

    if (entry != NULL) {
        entry->location = NULL;
        delete entry;
    }
}
 
void CacheHash::remove (VA addr,
                        HashTableNode<VA, CacheEntry*>** walk,
                        HashTableNode<VA, CacheEntry*>** prev)
{
    int place = hash(addr);
    HashTableNode<VA, CacheEntry*>** table =
        HashTable<VA, CacheEntry*>::getTable();

    if ((*walk)->data->isInVictimCache()) {
#ifdef XXX_ANM
        log->i("%lli:%s remove (%0x) %llx\n",
               global_sim->getSimclock(),
               owner->getName(),
               (uint)(*walk)->data,
               addr);
#endif
        uint size = victimCache.size();
        victimCache.remove((*walk)->data); // this should use pointer ==
        ASSERT(size == victimCache.size() + 1);
        (*walk)->data->setInVictimCache(false);
    } else {
        assocCounts[place]--;
    }


    if (*prev == NULL) {
        table[place] = (*walk)->next;
    } else {
        (*prev)->next = (*walk)->next;
    }
    HashTableNode<VA, CacheEntry*>* oldwalk = *walk;
    *walk = (*walk)->next;
    oldwalk->data->location = NULL;
    delete oldwalk;
    --length;
}

void CacheHash::clear () {
    HashTable<VA, CacheEntry*>::clear();
    victimCache.clear();

    for (uint i = 0; i < hashsize; i++) {
        assocCounts[i] = 0;
    }
}
